package org.wuxinshui.boosters.nowcoder.classicQuestion;

import java.util.HashMap;
import java.util.Map;

/**
 * CC3 多少个点位于同一直线
 * 描述
 * <p>
 * 对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上
 * <p>
 * 示例1
 * <p>
 * 输入：[(0,0),(0,1)]
 * 返回值：2
 * <p>
 * 示例2
 * 输入：
 * [(2,3),(3,3),(-5,3)]
 * 返回值：3
 * <p>
 * AI：
 * 为了解决这个问题，我们需要找到二维平面上最多有多少个点位于同一直线上。通过计算每个点与其他点构成的斜率，并统计相同斜率的点的数量，可以确定最多有多少点共线。
 * <p>
 * 方法思路
 * <p>
 * 问题分析：给定平面上的多个点，要求找出最多有多少点共线。共线的点意味着它们之间的斜率相同。
 * 关键思路：对于每个点，计算它与其他点的斜率。使用最大公约数（GCD）来标准化斜率，避免浮点数精度问题。垂直和水平线作为特殊情况处理。
 * 算法选择：使用哈希表来统计每个斜率出现的次数。对于每个点，计算与其他点的斜率，并记录重复点。最终结果为相同斜率点的最大数量加上重复点和自身。
 * 复杂度分析：算法的时间复杂度为O(n^2)，其中n是点的数量。每个点与其他点比较一次，计算斜率和更新哈希表。
 */
public class CC3MaxPoints_Practice {

    /**
     *
     * 代码解释
     * <p>
     * 初始化：检查点的数量，如果少于3个，直接返回点的数量。
     * 遍历每个点：对于每个点，初始化一个哈希表来存储斜率及其出现次数，并记录重复点。
     * 计算斜率：对于每对点，计算斜率。垂直和水平线作为特殊情况处理，其他情况使用GCD标准化斜率。
     * 统计最大值：更新当前点的最大共线点数，包括重复点和自身。
     * 返回结果：遍历所有点后，返回最大共线点数。
     * 该方法通过标准化斜率和高效统计，确保了正确性和性能。
     *
     * @param points Point类一维数组
     * @return int整型
     */
    public int maxPoints(Point[] points) {
        // write code here
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int maxCount = 0;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopeMap = new HashMap<>();
            int duplicate = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    duplicate++;
                    continue;
                }
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                String slopeKey;
                if (dx == 0) {
                    slopeKey = "0,1";
                } else if (dy == 0) {
                    slopeKey = "1,0";
                } else {
                    int g = gcd(Math.abs(dx), Math.abs(dy));
                    dx /= g;
                    dy /= g;
                    if (dy < 0) {
                        dx = -dx;
                        dy = -dy;
                    }
                    slopeKey = dx + "," + dy;
                }
                slopeMap.put(slopeKey, slopeMap.getOrDefault(slopeKey, 0) + 1);
            }
            int currentMax = 0;
            for (int count : slopeMap.values()) {
                if (count > currentMax) {
                    currentMax = count;
                }
            }
            currentMax += duplicate + 1;
            if (currentMax > maxCount) {
                maxCount = currentMax;
            }
        }
        return maxCount;
    }

    class Point {
        int x;
        int y;

        Point() {
            x = 0;
            y = 0;
        }

        Point(int a, int b) {
            x = a;
            y = b;
        }
    }

    public int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        CC3MaxPoints_Practice maxPoints=new CC3MaxPoints_Practice();
        System.out.println(maxPoints.gcd(40,90));
    }
}
